package question.solution897;

import question.SolutionTemplate;

import java.util.LinkedList;
import java.util.Queue;
import java.util.TreeSet;

public class Solution897 implements SolutionTemplate {

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    class BstResult{
        TreeNode head;
        TreeNode tail;
        BstResult(TreeNode h, TreeNode t){
            this.head = h;
            this.tail = t;
        }
    }

    public TreeNode increasingBST(TreeNode root) {
        BstResult bstResult = getBST(root);
        return bstResult.head;
    }

    public BstResult getBST(TreeNode node) {
        TreeNode myHead = null;
        TreeNode myTail = null;
        BstResult leftBST = null;
        if(null != node.left){
            leftBST = getBST(node.left);
        }
        if(null !=leftBST){
            myHead = leftBST.head;
            leftBST.tail.right = node;
        }else{
            myHead = node;
        }
        node.left=null;

        BstResult rightBST = null;
        if(null != node.right){
            rightBST = getBST(node.right);
        }
        if(null != rightBST){
            myTail = rightBST.tail;
            node.right = rightBST.head;
        }else{
            myTail = node;
        }
        return new BstResult(myHead, myTail);

    }

    private TreeNode generateTree(String[] strs){
        Queue<String> strQueue = new LinkedList<>();
        for(String str: strs){
            strQueue.add(str);
        }
        String headValue = strQueue.poll();
        TreeNode head = new TreeNode(Integer.valueOf(headValue));
        TreeNode pointer = head;
        Queue<TreeNode> nodeQueue = new LinkedList<>();

        do{
            if(strQueue.isEmpty()){
                break;
            }
            String leftSonNodeValue = strQueue.poll();
            if(!"null".equals(leftSonNodeValue)){
                TreeNode leftSonNode = new TreeNode(Integer.valueOf(leftSonNodeValue));
                pointer.left = leftSonNode;
                nodeQueue.add(leftSonNode);
            }
            String rightSonNodeValue = strQueue.poll();
            if(!"null".equals(rightSonNodeValue)){
                TreeNode rightSonNode = new TreeNode(Integer.valueOf(rightSonNodeValue));
                pointer.right = rightSonNode;
                nodeQueue.add(rightSonNode);
            }
            pointer = nodeQueue.poll();
        }while(true);
        return head;
    }

    @Override
    public void test() {
        String[] rootStr={"5","3","6","2","4","null","8","1","null","null","null","7","9"};
        TreeNode root = generateTree(rootStr);
        TreeNode result = increasingBST(root);
        System.out.println("");
    }

}
